package com.atguigu.sort;
import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * @author 龍
 * shell排序：插入排序的一种，简单的插入排序的改进版本，也称为缩小增量排序。
 * 规则：把记录按下标的一些增量分组，对每组使用直接插叙排序算法排序，随着增量逐渐减少
 * 每组包含的关键词越来越多，当增量减至1时，整个文件恰被分为一组，算法结束。
 * Shell排序的时间复杂度：nlogn
 * 交换法：花费时间为6s左右
 * 移位法：花费了大约35ms，效率非常的高。
 */
public class ShellSort {
    public static void main(String[] args) {
        /*int[] array=new int[]{8,9,1,7,2,3,5,4,6,0};

        shellSort2(array);
        System.out.println(Arrays.toString(array));*/
        int[] array = new int[80000];
        for (int i = 0; i < array.length; i++) {
            array[i] = new Random().nextInt(8000000);
        }
        //System.out.println(Arrays.toString(array));
        System.out.println("排序前的时间：" + System.currentTimeMillis());
        shellSort2(array);
        System.out.println("排序后的时间：" + System.currentTimeMillis());
        //System.out.println(Arrays.toString(array));

    }

    /**
     * 希尔排序的实现的方法1：交换的方式实现
     * @param arr：待排序的数组
     */
    public static void shellSort(int[] arr){
       /* //希尔排序的第一轮：将数组分为5组
        for (int i = 5; i < arr.length; i++) {
            for (int j = i-5; j >=0; j-=5) {
                //如果当前元素大于步长后的那个元素，说明需要进行交换
                if (arr[j]>arr[j+5]){
                    int temp=arr[j];
                    arr[j]=arr[j+5];
                    arr[j+5]=temp;
                }
            }
        }
        //将5/2，分为两组
        for (int i = 2; i < arr.length; i++) {
            for (int j = i-2; j >=0; j-=2) {
                //如果当前元素大于步长后的那个元素，说明需要进行交换
                if (arr[j]>arr[j+2]){
                    int temp=arr[j];
                    arr[j]=arr[j+2];
                    arr[j+2]=temp;
                }
            }
        }
        //第三轮
        for (int i = 1; i < arr.length; i++) {
            for (int j = i-1; j >=0; j-=1) {
                //如果当前元素大于步长后的那个元素，说明需要进行交换
                if (arr[j]>arr[j+1]){
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }*/
        //交换式希尔排序:
        for (int gap=arr.length/2;gap>0;gap/=2){
            for (int i = gap; i < arr.length; i++) {
                for (int j = i-gap; j >=0 ; j-=gap) {
                    if (arr[j]>arr[j+gap]){
                        int temp=arr[j];
                        arr[j]=arr[j+gap];
                        arr[j+gap]=temp;
                    }
                }
            }
        }
    }

    //移动式
    public static void shellSort2(int[] arr){
        for (int gap = arr.length/2; gap >0; gap/=2) {
            //从gap个元素，逐个对其所在的组进行直接插入排序
            for (int i = gap; i < arr.length; i++) {
                int j=i;
                int temp=arr[j];
                if(arr[j]<arr[j-gap]){
                    while(j-gap>=0&&temp<arr[j-gap]){
                        //移动
                        arr[j]=arr[j-gap];
                        j-=gap;
                    }
                    //此时找到了位置
                    arr[j]=temp;
                }
            }
        }
    }
}
